金发姑娘和 N 头牛

题目 金发姑娘和 N 头牛

image-1b011cf6

思路分析

image-98beb781

问题转化为 分别对三个区间里的每个元素加上x/y/z

对一个区间的元素同时加减某个数 —— 用差分

但是发现温度范围并没有给定 要找也只有一个1e9

所以不可能开这么大的数组去做差分操作

然后差分变前缀和是有个性质的 是0的话不影响结果

那么真正要用到的位置其实就只有几个

正负无穷 每轮的A 和B+1

（只要在这些地方做加减操作 其他的地方可以看做是0 没有意义）

那么就可以把这些数离散化出来

再用新映射的下标去做差分数组

再反过来构造前缀和——得到每头奶牛的产量

答案就是最大的那个 所以不断用max去做维护

所以发现差分和离散化有着有种联系

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=40010,INF=2e9;
vector<int> alls;
int A[N],B[N],b[N];
int n,x,y,z;

int find(int x){
    int l=0,r=alls.size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(alls[mid]>=x)
            r=mid;
        else
            l=mid+1;
    }
    return r;
    // return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

int main()
{
    cin>>n>>x>>y>>z;
    alls.push_back(-INF),alls.push_back(INF);
    for(int i=0;i<n;i++){
        cin>>A[i]>>B[i];
        alls.push_back(A[i]);
        alls.push_back(B[i]+1);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=0;i<n;i++){
        int l=find(A[i]),r=find(B[i]+1);
        b[0]+=x;
        b[l-1+1]-=x;
        b[l]+=y;
        b[r]-=y;
        b[r]+=z;
        b[alls.size()-1]-=z;
    }

    int res=0;
    for(int i=0;i<alls.size();i++){
        if(i)
            b[i]+=b[i-1];
        res=max(b[i],res);
    }

    cout<<res<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 粉刷栅栏 🏠 00-刷题理模型 ➡️ 非零段划分